package com.test;


import java.util.LinkedList;
import java.util.Map;

/**
 * @author zack
 * @create 2019-07-20-12:14
 */

public class Graph {
    private int vertexSize;
    private int[] vertexs;
    private static int MAX_WEIGHT = 1000;
    private int[][] matrix;
    private boolean[] isVisited;
//
    public int getOutdegree(int index) {
        int x = 0;
        for (int j = 0; j < matrix[index].length; j++) {
            int weight = matrix[index][j];
            if (weight > 0 && weight < MAX_WEIGHT) {
                x++;
            }
        }
        return x;
    }

    /**
     * 初始化一个图，用户输入图中节点的个数
     *
     * @param vertexSize
     * @Param matrix: 节点之间的边
     * @Param vertex: 所有节点放到一个数组中
     * @Param isVisited: 初始化一个boolean数组来确保该点是否被遍历过
     */
    public Graph(int vertexSize) {
        this.vertexSize = vertexSize;
        matrix = new int[vertexSize][vertexSize];
        vertexs = new int[vertexSize];
        for (int x = 0; x < vertexSize; x++) {
            vertexs[0] = x;
        }
        isVisited = new boolean[vertexSize];
    }

    public int getVertexSize() {
        return vertexSize;
    }

    public void setVertexSize(int vertexSize) {
        this.vertexSize = vertexSize;
    }

    public int[] getVertexs() {
        return vertexs;
    }

    public void setVertexs(int[] vertexs) {
        this.vertexs = vertexs;
    }

    public static int getMaxWeight() {
        return MAX_WEIGHT;
    }

    public static void setMaxWeight(int maxWeight) {
        MAX_WEIGHT = maxWeight;
    }

    public int[][] getMatrix() {
        return matrix;
    }

    public void setMatrix(int[][] matrix) {
        this.matrix = matrix;
    }

    /**
     * 得到第一个邻接点
     *
     * @param
     */
    public int getFirstNeighbor(int index) {
        int weight = 0;
        for (int x = 0; x < vertexSize; x++) {
            weight = matrix[index][x];
            if (weight > 0 && weight < MAX_WEIGHT) {
                return x;
            }
        }
        return -1;
    }

    /**
     * 得到相对于第一个临界节点的
     *
     * @param v     当前的遍历的节点
     * @param index 当前的遍历的节点
     */
    public int getNextNeighbor(int v, int index) {
        int weight = 0;
        for (int x = index + 1; x < vertexSize; x++) {
            weight = matrix[v][x];
            if (weight > 0 && weight < MAX_WEIGHT) {
                return x;
            }
        }
        return -1;
    }

    /**
     * 深度遍历（对于连通图）
     *
     * @param v 是一个随意一个点
     */
    public void depthFirstSearch(int v) {
        isVisited[v] = true;
        int w = getFirstNeighbor(v);
        while (w != -1) {
            if (!isVisited[w]) {
                System.out.println("访问了" + w + "顶点");
                depthFirstSearch(w);
            }
            w = getNextNeighbor(v, w);
        }

    }

    /**
     * 所有图都可用的dfs遍历
     */
    public void depthFirstSearch() {
        isVisited = new boolean[vertexSize];
        for (int x = 0; x < vertexSize; x++) {
            if (!isVisited[x]) {
                System.out.println("访问了" + x + "顶点");
                depthFirstSearch(x);
            }
        }
        isVisited = new boolean[vertexSize];
    }

    /**
     * 所有图都可用的bfs遍历
     *
     * @param
     */
    public void broadFirstSearch() {
        isVisited = new boolean[vertexSize];
        for (int i = 0; i < vertexSize; i++) {
            if (!isVisited[i]) {
                broadFirstSearch(i);
            }
        }
        isVisited = new boolean[vertexSize];
    }

    /**
     * 强链接的图bfs
     *
     * @param x
     */
    private void broadFirstSearch(int x) {
        int u, w;
        LinkedList<Integer> queue = new LinkedList<>();
        System.out.println("访问到了" + x + "节点");
        isVisited[x] = true;
        queue.add(x);
        while (!queue.isEmpty()) {
            u = (Integer) (queue.removeFirst()).intValue();
            w = getFirstNeighbor(x);
            while (w != -1) {
                if (!isVisited[w]) {
                    System.out.println("访问到了：" + w + "顶点");
                    isVisited[w] = true;
                    queue.add(w);
                }
                w = getNextNeighbor(u, w);
            }
        }
    }

    /**
     * 普利姆算法
     *
     * @param
     */
    public void prim() {
        int lowcost[] = new int[vertexSize];//最小代价权值数组
        int adjvex[] = new int[vertexSize];//放顶点权值
        int min, minId, sum = 0;
        for (int i = 1; i < vertexSize; i++) {
            lowcost[i] = matrix[0][i];
        }
        for (int i = 1; i < vertexSize; i++) {
            min = MAX_WEIGHT;
            minId = 0;
            for (int j = 0; j < vertexSize; j++) {
                if (lowcost[j] < min && lowcost[j] > 0) {
                    min = lowcost[j];
                    minId = j;
                }
            }
            System.out.println("顶点：" + adjvex[minId] + "权值：" + min);
            sum += min;
            // lowcost[minId] = 0;
            for (int j = 1; j < vertexSize; j++) {
                if (lowcost[j] != 0 && matrix[minId][j] < lowcost[j]) {
                    lowcost[j] = matrix[minId][j];
                    adjvex[j] = minId;
                }
            }
        }
        System.out.println("最小值" + sum);

    }

    public static void main(String args[]) {
        Graph graph = new Graph(9);
        int a0[] = {0, 10, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT};
        int a1[] = {10, 0, 18, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, MAX_WEIGHT, 12};
        int a2[] = {MAX_WEIGHT, MAX_WEIGHT, 0, 22, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 8};
        int a3[] = {MAX_WEIGHT, MAX_WEIGHT, 22, 0, 20, MAX_WEIGHT, MAX_WEIGHT, 16, 21};
        int a4[] = {MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 20, 0, 26, MAX_WEIGHT, 7, MAX_WEIGHT};
        int a5[] = {11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 26, 0, 17, MAX_WEIGHT, MAX_WEIGHT};
        int a6[] = {MAX_WEIGHT, 16, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 17, 0, 19, MAX_WEIGHT};
        int a7[] = {MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, 7, MAX_WEIGHT, 19, 0, MAX_WEIGHT};
        int a8[] = {MAX_WEIGHT, 12, 8, 21, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 0};
        graph.matrix[0] = a0;
        graph.matrix[1] = a1;
        graph.matrix[2] = a2;
        graph.matrix[3] = a3;
        graph.matrix[4] = a4;
        graph.matrix[5] = a5;
        graph.matrix[6] = a6;
        graph.matrix[7] = a7;
        graph.matrix[8] = a8;
        // System.out.println(graph.getOutdegree(2));
        //graph.depthFirstSearch(1);
        graph.prim();
    }
}
